package com.san.quicksort;

import java.util.Scanner;

public class Quicksort {

	public static void main(String[] args) {
		quickSort();

	}

	
	private static void quickSort() {
		// 数组初始化
		Scanner sc = new Scanner(System.in);
		System.out.println("请输入要排序数组的个数：");
		int count = sc.nextInt();  // 数的个数
		
		int[] arr = new int[count];   // 创建数组
		for (int i = 0; i < count; i++) {    // 初始化数组
			System.out.println("请输入数组的第" + (i + 1) + "个元素：");
			int input = sc.nextInt();
			arr[i] = input;
		}
		doQuickSort(arr, 0, count - 1);
		printArr(arr);

	}

	// 快速排序算法
	/**
	 * @param arr数组
	 * @param left从左往右查找的下表
	 * @param right从右往左查找的下表
	 */
	private static void doQuickSort(int[] arr, int left, int right) {
		if (left < right) {
			// 必须保证从左往右采取的数大于从右往左采取的数
			// 定义最左边，和最右边，并分别用其他的代替变换的序号
			int lp = left;
			int rp = right;
			// 定义最左边的元素为基准
			int val = arr[lp];
			while (lp < rp) {
				/**
				 * 从右往左找比基准值小的数
				 */
				while (lp < rp && arr[rp] >= val) {
					rp--;
				} // 否则的话，即找到比基准值小的数时，进行交换
				int temp = arr[rp];
				arr[rp] = arr[lp];
				arr[lp] = temp;
				/**
				 * 从左往右找比基准值小的数
				 */
				while (lp < rp && arr[lp] <= val) {
					lp++;
				} // 否则的话，从左往右找到的比基准值小的数与基准值进行交换
				temp = arr[lp];
				arr[lp] = arr[rp];
				arr[rp] = temp;
			}
			// 进行递归调用
			doQuickSort(arr, left, lp - 1);// 左边的部分
			doQuickSort(arr, lp + 1, right);// 右边的部分

		}

	}

	// 打印数组
	private static void printArr(int[] arr) {
		for (int i : arr) {
			System.out.print(" " + i);

		}
		System.out.println();
	}
}
